/*
 * Copyright 2020-2030 the original author or authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package collections.list;

import collections.TimSort;

import java.util.Comparator;

/**
 * @author Neil Wang
 * @version 1.0.0
 * @date 2021/6/11 10:14 上午
 */
public class Arrays {
    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) sort(a);
        else {
            if (LegacyMergeSort.userRequested) legacyMergeSort(a, c);
//            else TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
        }
    }

    private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
        T[] aux = a.clone();
        if (c == null) mergeSort(aux, a, 0, a.length, 0);
        else mergeSort(aux, a, 0, a.length, 0, c);
    }


    private static final int INSERTION_SORT_THRESHOLD = 7;

    @SuppressWarnings({"unchecked", "rawtypes"})
    private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) {
        int length = high - low;
        if (length < INSERTION_SORT_THRESHOLD) {
            for (int i = low; i < high; i++)
                for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
                    swap(dest, j, j - 1);
            return;
        }
        int destLow = low;
        int destHigh = high;
        low += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);
        if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }
        for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable) src[p]).compareTo(src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

    @SuppressWarnings({"rawtypes", "unchecked"})
    private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c) {
        int length = high - low;
        if (length < INSERTION_SORT_THRESHOLD) {
            for (int i = low; i < high; i++)
                for (int j = i; j > low && c.compare(dest[j - 1], dest[j]) > 0; j--)
                    swap(dest, j, j - 1);
            return;
        }
        int destLow = low;
        int destHigh = high;
        low += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off, c);
        mergeSort(dest, src, mid, high, -off, c);
        if (c.compare(src[mid - 1], src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }
        for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

    private static void swap(Object[] x, int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

    private static void sort(Object[] a) {

    }

    /**
     * 可以使用系统属性选择旧的合并排序实现(为了与损坏的比较器兼容)。由于循环依赖关系，不能在外围类中是静态布尔值。将在未来的版本中删除。
     */
    static final class LegacyMergeSort {
        private static final boolean userRequested =
                java.security.AccessController.doPrivileged(
                        new sun.security.action.GetBooleanAction(
                                "java.util.Arrays.useLegacyMergeSort"));
    }
}
